<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>skyline</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="skyline">skyline</h1>
<h1 id="1-my-solution">1. my solution</h1>
<p>LC 218</p>
<ul>
<li><a href="https://leetcode.com/problems/the-skyline-problem/">https://leetcode.com/problems/the-skyline-problem/</a></li>
</ul>
<h2 id="11-v1-借用了结束时间来把过期的大楼pop出来-onlgn">1.1 v1, 借用了结束时间来把过期的大楼pop出来， O(nlgn)</h2>
<ul>
<li><a href="https://leetcode.com/problems/the-skyline-problem/discuss/61261/10-line-Python-solution-104-ms">https://leetcode.com/problems/the-skyline-problem/discuss/61261/10-line-Python-solution-104-ms</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">getSkyline</span><span class="hljs-params">(self, buildings: List[List[int]])</span> -&gt; List[List[int]]:</span>
        h = [(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, float(<span class="hljs-string">'inf'</span>))]   <span class="hljs-comment"># 这里h必须有初始值</span>
        events = []
        <span class="hljs-keyword">for</span> L,R,H <span class="hljs-keyword">in</span> buildings:
            events.append((L, R, H))
            events.append((R, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>))
            
        <span class="hljs-comment"># 经过排序后，满足下面的条件</span>
        <span class="hljs-comment"># (1)先开始的大楼出现在后开始的大楼前面</span>
        <span class="hljs-comment"># (2)同一个坐标，开始多个大楼， 先出现高的大楼(添加顺序)</span>
        <span class="hljs-comment"># (3)同一个坐标，结束多个大楼， 先出现矮的大楼(删除顺序)</span>
        <span class="hljs-comment"># (4)同一个坐标，既有大楼开始，又有大楼结束， 开始的大楼出现在前面</span>

        events.sort(key=<span class="hljs-keyword">lambda</span> x: (x[<span class="hljs-number">0</span>], -x[<span class="hljs-number">2</span>]))  <span class="hljs-comment"># 这里排序很关键，最开始写错了。</span>
        
        ans = []
        <span class="hljs-keyword">for</span> L, R, H <span class="hljs-keyword">in</span> events:
            <span class="hljs-keyword">while</span> h <span class="hljs-keyword">and</span> h[<span class="hljs-number">0</span>][<span class="hljs-number">2</span>] &lt;= L:
                heapq.heappop(h)
                
            <span class="hljs-keyword">if</span> R &gt; <span class="hljs-number">0</span>:
                heapq.heappush(h, (-H, L, R))
                
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> ans <span class="hljs-keyword">or</span> ans[<span class="hljs-number">-1</span>][<span class="hljs-number">1</span>] != -h[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>]:
                ans.append((L, -h[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>]))
                
        <span class="hljs-keyword">return</span> ans
    
    
        
</div></code></pre>
<h2 id="12-如果单纯用heapq的话因为python-的heapq删除效率低整个算法就要on2">1.2 如果单纯用heapq的话，因为python 的heapq删除效率低，整个算法就要O(n^2)</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq
<span class="hljs-comment"># 参考 https://zhuanlan.zhihu.com/p/48403793</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">getSkyline</span><span class="hljs-params">(self, buildings: List[List[int]])</span> -&gt; List[List[int]]:</span>
        
        events = []
        <span class="hljs-keyword">for</span> L,R,H <span class="hljs-keyword">in</span> buildings:
            events.append((L,H,<span class="hljs-number">1</span>))
            events.append((R,H,<span class="hljs-number">0</span>))
        <span class="hljs-comment"># 一定要这样排序，为了解决不同大楼坐标重合或者高度重合的问题</span>
        <span class="hljs-comment"># (1)同一个坐标出现多个高楼, 高度高的出现在前面</span>
        <span class="hljs-comment"># (2)同一个坐标既有高楼开始，又有高楼结束， 开始的记录出现在前面</span>
        events.sort(key = <span class="hljs-keyword">lambda</span> x: (x[<span class="hljs-number">0</span>], -x[<span class="hljs-number">1</span>], -x[<span class="hljs-number">2</span>])) 
                                                       
        
        heap = [<span class="hljs-number">0</span>] <span class="hljs-comment"># 初始高度记录是0, 对后面的判断很重要</span>
        ans = []
        <span class="hljs-keyword">for</span> pos, height, flag <span class="hljs-keyword">in</span> events:
            <span class="hljs-comment">#print(f"{pos} {height} {flag} {heap}")</span>
            pre_highest = heap[<span class="hljs-number">0</span>]
            <span class="hljs-keyword">if</span> flag == <span class="hljs-number">1</span>: <span class="hljs-comment"># start event</span>
                heapq.heappush(heap, -height)
            <span class="hljs-keyword">else</span>: <span class="hljs-comment">#end event</span>
                delete_element_index = heap.index(-height)
                heap[delete_element_index] = heap[<span class="hljs-number">-1</span>]
                heap.pop()
                heapq.heapify(heap)
                <span class="hljs-comment"># heap.remove(-height) 不能直接remove, 这会破坏heap的特性</span>
            <span class="hljs-keyword">if</span> heap[<span class="hljs-number">0</span>] != pre_highest: <span class="hljs-comment"># 最大高度发生了变化, 坐标也发生了变化， 就记录关键点</span>
                <span class="hljs-comment"># 关键点的记录是(pos, -heap[0]), 而不是 (pos, height)</span>
                <span class="hljs-keyword">if</span> ans <span class="hljs-keyword">and</span> pos == ans[<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>]:  <span class="hljs-comment"># 如果大楼结束点的坐标相同</span>
                    ans[<span class="hljs-number">-1</span>] = (pos, -heap[<span class="hljs-number">0</span>]) 
                <span class="hljs-keyword">else</span>:  <span class="hljs-comment"># 如果大楼结束点的坐标不同</span>
                    ans.append((pos, -heap[<span class="hljs-number">0</span>]))
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<p>今天看了这篇文章以后，才知道，上面的1.2 是扫描线算法。</p>
<p><a href="https://leetcode.com/problems/the-skyline-problem/discuss/372084/c%2B%2B-and">https://leetcode.com/problems/the-skyline-problem/discuss/372084/c%2B%2B-and</a></p>
<p>但是python没有提供类似于c==里面的multiset 或者 Java的TreeMap 这样的标准库.  所以删除元素的时候，效率就比较低。</p>
<p><a href="https://stackoverflow.com/questions/17346905/is-there-a-python-equivalent-for-c-multisetint">https://stackoverflow.com/questions/17346905/is-there-a-python-equivalent-for-c-multisetint</a></p>
<p><a href="https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree">https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree</a></p>
<p>时间复杂度还是O(n^2), 如果python能有multiset或者TreeMap, 就可以降低为O(nlgn)</p>
<p>如果要提高效率，就只能在大顶堆里面，同时保存大楼的高度和结束的坐标， 这样才能快速删除掉大楼,  就像1.1解法那样</p>
<h1 id="2-tushare-solution-用了java的treemap">2. tushare solution, 用了java的TreeMap</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=GSBLe8cKu0s">https://www.youtube.com/watch?v=GSBLe8cKu0s</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/geometry/SkylineDrawing.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/geometry/SkylineDrawing.java</a></li>
</ul>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.geometry;

<span class="hljs-keyword">import</span> java.util.*;

<span class="hljs-comment">/**
 * Date 01/07/2016
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Given skyline of a city merge the buildings
 *
 * Time complexity is O(nlogn)
 * Space complexity is O(n)
 *
 * References
 * https://leetcode.com/problems/the-skyline-problem/
 * https://leetcode.com/discuss/67091/once-for-all-explanation-with-clean-java-code-nlog-time-space
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">SkylineDrawing</span> </span>{

    <span class="hljs-comment">/**
     * Represents either start or end of building
     */</span>
    <span class="hljs-keyword">static</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BuildingPoint</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Comparable</span>&lt;<span class="hljs-title">BuildingPoint</span>&gt; </span>{
        <span class="hljs-keyword">int</span> x;
        <span class="hljs-keyword">boolean</span> isStart;
        <span class="hljs-keyword">int</span> height;

        <span class="hljs-meta">@Override</span>
        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compareTo</span><span class="hljs-params">(BuildingPoint o)</span> </span>{
            <span class="hljs-comment">//first compare by x.</span>
            <span class="hljs-comment">//If they are same then use this logic</span>
            <span class="hljs-comment">//if two starts are compared then higher height building should be picked first</span>
            <span class="hljs-comment">//if two ends are compared then lower height building should be picked first</span>
            <span class="hljs-comment">//if one start and end is compared then start should appear before end</span>
            <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.x != o.x) {
                <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.x - o.x;
            } <span class="hljs-keyword">else</span> {
                <span class="hljs-keyword">return</span> (<span class="hljs-keyword">this</span>.isStart ? -<span class="hljs-keyword">this</span>.height : <span class="hljs-keyword">this</span>.height) - (o.isStart ? -o.height : o.height);
            }
        }
     }

    <span class="hljs-keyword">public</span> List&lt;<span class="hljs-keyword">int</span>[]&gt; getSkyline(<span class="hljs-keyword">int</span>[][] buildings) {

        <span class="hljs-comment">//for all start and end of building put them into List of BuildingPoint</span>
        BuildingPoint[] buildingPoints = <span class="hljs-keyword">new</span> BuildingPoint[buildings.length*<span class="hljs-number">2</span>];
        <span class="hljs-keyword">int</span> index = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> building[] : buildings) {
            buildingPoints[index] = <span class="hljs-keyword">new</span> BuildingPoint();
            buildingPoints[index].x = building[<span class="hljs-number">0</span>];
            buildingPoints[index].isStart = <span class="hljs-keyword">true</span>;
            buildingPoints[index].height = building[<span class="hljs-number">2</span>];

            buildingPoints[index + <span class="hljs-number">1</span>] = <span class="hljs-keyword">new</span> BuildingPoint();
            buildingPoints[index + <span class="hljs-number">1</span>].x = building[<span class="hljs-number">1</span>];
            buildingPoints[index + <span class="hljs-number">1</span>].isStart = <span class="hljs-keyword">false</span>;
            buildingPoints[index + <span class="hljs-number">1</span>].height = building[<span class="hljs-number">2</span>];
            index += <span class="hljs-number">2</span>;
        }
        Arrays.sort(buildingPoints);

        <span class="hljs-comment">//using TreeMap because it gives log time performance.</span>
        <span class="hljs-comment">//PriorityQueue in java does not support remove(object) operation in log time.</span>
        TreeMap&lt;Integer, Integer&gt; queue = <span class="hljs-keyword">new</span> TreeMap&lt;&gt;();
        <span class="hljs-comment">//PriorityQueue&lt;Integer&gt; queue1 = new PriorityQueue&lt;&gt;(Collections.reverseOrder());</span>
        queue.put(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>);
        <span class="hljs-comment">//queue1.add(0);</span>
        <span class="hljs-keyword">int</span> prevMaxHeight = <span class="hljs-number">0</span>;
        List&lt;<span class="hljs-keyword">int</span>[]&gt; result = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
        <span class="hljs-keyword">for</span>(BuildingPoint buildingPoint : buildingPoints) {
            <span class="hljs-comment">//if it is start of building then add the height to map. If height already exists then increment</span>
            <span class="hljs-comment">//the value</span>
            <span class="hljs-keyword">if</span> (buildingPoint.isStart) {
                queue.compute(buildingPoint.height, (key, value) -&gt; {
                    <span class="hljs-keyword">if</span> (value != <span class="hljs-keyword">null</span>) {
                        <span class="hljs-keyword">return</span> value + <span class="hljs-number">1</span>;
                    }
                    <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
                });
              <span class="hljs-comment">//  queue1.add(cp.height);</span>
            } <span class="hljs-keyword">else</span> { <span class="hljs-comment">//if it is end of building then decrement or remove the height from map.</span>
                queue.compute(buildingPoint.height, (key, value) -&gt; {
                    <span class="hljs-keyword">if</span> (value == <span class="hljs-number">1</span>) {
                        <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
                    }
                    <span class="hljs-keyword">return</span> value - <span class="hljs-number">1</span>;
                });
               <span class="hljs-comment">// queue1.remove(cp.height);</span>
            }
            <span class="hljs-comment">//peek the current height after addition or removal of building x.</span>
            <span class="hljs-keyword">int</span> currentMaxHeight = queue.lastKey();
            <span class="hljs-comment">//int currentMaxHeight = queue1.peek();</span>
            <span class="hljs-comment">//if height changes from previous height then this building x becomes critcal x.</span>
            <span class="hljs-comment">// So add it to the result.</span>
            <span class="hljs-keyword">if</span> (prevMaxHeight != currentMaxHeight) {
                result.add(<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{buildingPoint.x, currentMaxHeight});
                prevMaxHeight = currentMaxHeight;
            }
        }
        <span class="hljs-keyword">return</span> result;
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span> </span>{
        <span class="hljs-keyword">int</span> [][] buildings = {{<span class="hljs-number">1</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>},{<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">4</span>},{<span class="hljs-number">2</span>,<span class="hljs-number">6</span>,<span class="hljs-number">2</span>},{<span class="hljs-number">8</span>,<span class="hljs-number">11</span>,<span class="hljs-number">4</span>}, {<span class="hljs-number">7</span>,<span class="hljs-number">9</span>,<span class="hljs-number">3</span>},{<span class="hljs-number">10</span>,<span class="hljs-number">11</span>,<span class="hljs-number">2</span>}};
        SkylineDrawing sd = <span class="hljs-keyword">new</span> SkylineDrawing();
        List&lt;<span class="hljs-keyword">int</span>[]&gt; criticalPoints = sd.getSkyline(buildings);
        criticalPoints.forEach(cp -&gt; System.out.println(cp[<span class="hljs-number">0</span>] + <span class="hljs-string">" "</span> + cp[<span class="hljs-number">1</span>]));

    }
}
</div></code></pre>
<h1 id="3-下面是线段树的解法">3. 下面是线段树的解法</h1>
<p>太复杂了，已有的线段树解法都没看懂。</p>
<h1 id="4-官方标准答案的分治法">4. 官方标准答案的分治法。</h1>
<p><a href="https://leetcode.com/problems/the-skyline-problem/solution/">https://leetcode.com/problems/the-skyline-problem/solution/</a></p>
<p>这里还有一个总结  <a href="https://zhuanlan.zhihu.com/p/79857068">https://zhuanlan.zhihu.com/p/79857068</a></p>

    </body>
    </html>